#include<bits/stdc++.h>
#define int long long
using namespace std;
int q,a,b,prim[1000010],p[10000010],cnt,fj[10000010];
int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}
int xxs(){
	for(int i=2;i<=10000000;i++){
		if(!p[i]) prim[++cnt]=i,fj[i]=i;
		for(int j=1;j<=cnt;j++){
			if(i*prim[j]>10000000) break;
			p[i*prim[j]]=1,fj[i*prim[j]]=prim[j];
			if(i%prim[j]==0) break;
		}
	}
}
int solve(int x,int y){
	int fx=fj[x],fy=fj[y];
	if(fx==x&&fy==y) return min((x+y)*2,x*y);
	int res=solve(fx,fy);
	if(fx!=x) res+=x;
	if(fy!=y) res+=y;
	return res;
}
signed main(){
	freopen("never.in","r",stdin);
	freopen("never.out","w",stdout);
	xxs();
	scanf("%lld",&q);
	while(q--){
		scanf("%lld%lld",&a,&b);
		if(b%a==0){
			printf("%lld\n",b);
			continue;
		}
		if(gcd(a,b)!=1){
			printf("%lld\n",a+b);
			continue;
		}
		printf("%lld\n",solve(a,b));
	}
	return 0;
}
